SPACE 2/SPACE - Library 2 - Volume 1.iso/utility/511/turing/turing.asc

Text File | 1991-02-13 | 11.8 KB | 414 lines

                      Turing Machine Simulation

                               by

                   Robert and Alexander Feinman



                          Introduction

     This program simulates a Turing Machine, a theoretical type

of computer first described by the mathematican Alan Turing in

the 1930's. Turing invented this model to study basic problems in

a branch of mathematics known as predicate calculus. His intent

was to design a machine that could represent any algorithm in a

series of finite states (program steps). While this model leads

to some interesting studies in mathematics it is also possible to

consider the Turing machine as a a prototype of a digital

computer.

     Basically a Turing machine can be represented by a

mechanical device. Imagine a computer consisting of a long tape

on which can be placed a series of symbols drawn from a list. For

our purposes it is sufficient to assume only two symbols, zero

and one. Above this tape is a read/write head. First, this head

reads the mark on the tape at the current position. The value of

the mark causes the machine to take an action determined by the

state of its control program. Second, a new symbol is written to

the tape on the current position. Third, The tape moves one space

either right or left. Finally, the control program jumps to a new

step. The control program has a series of these statements

similar to the lines of a conventional programming language. Each

of these statements is called one of the possible states of the

machine. The programming language consists of only four

components: the step number, the symbol to write, the direction

to move, and the number of the next step to execute. Each step

has two parts: the first specifies the action to take if the tape

contains a zero and the other the action to take if it contains a

one. Thus a typical step might be represented as follows:


Step x:   If tape = 0:

               Write 1, Move tape left, Jump to step n.

          Else

               Write 0, Move tape right, Jump to step m.


     Turing showed that this simple set of instructions can be

used to generate any actions that a large-scale computer can

perform. Over the past few years there have been a number of

articles on Turing Machines giving sample implementations for a

variety of microcomputers. I decided to implement a simulation

for the Atari ST which makes use of the graphic abilities of the

computer. The creation of the Degas background was done by my son

Alex, who also helped with some of the final testing and debugging.

The program was written in GFA Basic and compiled. It runs in low

resolution only. I used a trick to incorporate the Degas picture

into the actual executable file, thus avoiding the need for data

statements or a separate picture file.

     Questions and comments can be directed to:

Compuserve: 71350,3607

Genie: RFEINMAN

Internet: [e-mail]

Bitnet: [e-mail]



                         Program Usage


     The program displays a whimsical screen representing a

factory with a conveyor belt near the bottom of the screen acting

as the tape. Referring to the figure we see the read/write head

shown by an arrow pointing to the tape. In addition there are

four boxes in the upper left corner connected by pipes with

arrows in them. Within these boxes are groups of two buttons used

to program the computer. This group is used to enter a program

step. Below this is a selector box with a handle labeled MODE.

Clicking in this box allows the user to cycle through the various

functions that the simulation permits. In the INPUT mode enter a

program step by clicking on one button in the MOVE group, one

button in the WRITE group and then click on the up/down arrows in

the JUMP group until the desired number appears in the STEP

window. At this point click in the STEP window to select the

state to jump to. The sequence is ended by pressing DO.

     The program automatically numbers each statement as it is

entered and shifts from the 'read a zero' case to the 'read a

one' case for each program step. These steps are shown in the

window labeled SOURCE LISTING on the right side. the END button

is a special case; it is only used to enter a step in which the

Turing program is to terminate.

     Returning to the MODE box we can cycle through the other

functions. These appear within the window and are selected by

pressing the OK button. The modes are Trace, Input, Tape, Run,

Edit, Print, Load, Save, Exit, Clear and Erase.


     Trace runs an existing program and prints a step-by-step

       trace of each instruction executed to an attached printer.


     Input allows a new program to entered, as described above.


     Tape is for setting initial conditions on the tape. This is

       done by clicking on the boxes on the tape. The

       values will alternate between zero and one. The tape

       can be scrolled by using the long left- and right-pointing

       arrows at the bottom sides of the screen.


     Run starts the program. Execution can be stopped at any time

        by clicking the left button. The tape can also be modified

        after the program is stopped in this mode without going back

        to the tape mode. Clicking on OK again will restart the

        program with the new setup. In addition the Turbo box can

        be clicked before starting the program to have it run in

        an accelerated mode without sound effects.


     Edit allows an existing program to be modified. To use edit

       mode select this mode and click on the JUMP arrows until

       the step you wish to edit is in the step window. Then

       click inside the STEP box and that line will be displayed

       in the source window. It is necessary to replace all six

       parts of information for the step during an edit. Use

       the same techniques as for entering a step originally.

       If an existing program needs more steps added INPUT

       mode can also be used. New steps will automatically be

       entered at the end.


     Print will output a listing of the control program to the

       printer.


     Load and Save allow programs to be read from or written to

       disk. The default extension for these programs is ".TUR".


     Exit ends the simulation and returns you to the desktop.


     Clear erase the current program from memory.


     Erase clears the tape back to all zeros.


     When the program first starts, the SOURCE LISTING window

will give some initial help. In addition a series of prompts are

shown along the bottom as the program is used. The two arrows

above and below the Listing window allow the source to be

scrolled.


     Each line of the program is represented by three symbols.

The step number is followed by an arrow indicating the direction

the tape will move, then a zero or one to show what will be

written and lastly the step number to jump to. This sequence is

on the left for the 'read a zero' case and on the right for the

'read a one'. On a printed listing the left and right arrows are

replaced by plus and minus one. The box labeled END generates a

cross in a circle. This special symbol is placed to indicate that

the control program is not to proceed past this step.



                             Entering a program

     To enter a typical program step click on MODE until the word

INPUT appears, then click on OK. Now select one MOVE button, one

WRITE button and use JUMP arrows to scroll the window to the step

required. Click on STEP to enter this as well. If everything is

to your liking click on DO and the cursor will move to the right

side of the source window for the other half of the program step.

Before pressing DO any value can be changed by clicking on the

desired replacement button. The three values needed for each half

of the program can be entered in any order.

     When the program has been entered click on MODE until TAPE

appears in the window, the press OK. Now click on the tape to set

or clear ones. The tape can be scrolled to enter more data, if

needed. The box labeled MARK shows the position of the read/write

head over the tape. For faster positioning, this box can be clicked

on. Enter a number within the indicated limits and the pointer will

jump to that spot. While a true Turing machine should have an

infinite tape, I have restricted this to several thousand

positions as a practical limit. If the tape progresses to either end

the program will stop.

     When all is set, change the mode to RUN or TRACE and press

OK. Also set Turbo if desired; this will elimante the sound

effects and speed up the execution considerably. The machine

will immediately begin executing your program. The source window

will show the current step being executed and a small arrow will

indicate which case (zero or one) is being taken. The program

can be stopped at any time by pressing the left mouse button.

     The program can be reviewed by clicking in the SOURCE

LISTING window. The first twelve steps will be shown. Use the

small arrows above and below the window to scroll the listing.


                        Sample Turing Programs

     There are some sample programs in the package. The first,

NOT.TUR changes every one to a zero and vice versa. The second,

ADD.TUR, adds two numbers together. The numbers are represented

on the tape by a series of ones equal to the value of the first

number, a zero, and then the next number represented by ones

again. Start the program from the left side and it will combine

the two numbers together by removing the zero between them.

     A more interesting program to try is to multiply two numbers

together. The trick here is to treat multiplication as successive

addition. First write a routine which copies the left hand string

to the end of the right one. Then use this subroutine in a longer

program which copies the left number as many times as there are

ones in the original string.

     Another interesting class of Turing programs are called Busy

Beavers. These programs attempt to write the longest string of

successive ones to a tape initially filled with zeros before

halting. This problem has been solved for Turing machines having

up through four states. The longest five state Busy Beaver found

to date generates 1915 ones before halting. The listings for all

of these are included. In addition I include a Busy Beaver which

spends much time moving to and fro, but which ends up by doing

nothing. This class of programs are called Dizzy Beavers. Refer

to the bibliography for the source of these Turing programs.

     If you develop any interesting Turing programs, please post

them on one of the public bulletin boards, for others to see.


                           Bibliography

     For further reading on this subject you can consult the

following references:


Hopcroft, John E., "Turing Machines", Scientific American, May

1984, pp. 86-98.


Malitz, Isaac, "The Turing Machine", Byte, November 1987, pp.

345-358.


Dewdney, A.K., "Busy Beavers", The Armchair Universe, W.H.

Freeman, New York, 1988, pp. 160-171.


Turing, A., "On the Computable Numbers, with an Application to

the Entschiedungsproblem", Proceedings of the London Mathematical

Society, Series 2-42, 1936. pp. 230-265.